package hash;

import java.util.NoSuchElementException;
import java.util.TreeMap;

/**
 * 基于TreeMap的查找表实现
 * @author yuisama
 * @date 2021/12/15 17:41
 **/
public class HashTableByTree<K,V> {
    // 具体存储元素的TreeMap数组
    private TreeMap<K,V>[] table;
    // 当前存储的元素个数
    private int size;
    // 数组大小
    private int M;

    // 扩容上限 = size / M,平均查找长度
    private static final int UPPER_THRESHOLD = 10;
    // 默认数组大小
    private static final int DEFAULT_CAPACITY = 16;

    public HashTableByTree() {
        this(DEFAULT_CAPACITY);
    }

    public HashTableByTree(int M) {
        this.M = M;
        table = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            table[i] = new TreeMap<>();
        }
    }

    /**
     * 计算key对应的索引下标
     * @param key
     * @return
     */
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    /**
     * 向哈希表中添加一对元素
     * @param key
     * @param value
     */
    public void add(K key,V value) {
        // 先根据key的hash找到TreeMap数组中具体的那个Map
        TreeMap<K,V> map = table[hash(key)];
        if (!map.containsKey(key)) {
            size ++;
            if (size >= M * UPPER_THRESHOLD) {
                resize(M * 2);
            }
        }
        map.put(key,value);
    }

    /**
     * 重新调整哈希表大小
     * @param newM
     */
    private void resize(int newM) {
        TreeMap<K,V>[] newTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newTable[i] = new TreeMap<>();
        }
        int oldM = M;
        this.M = newM;
        // 取出原先数组的值放入新table
        for (int i = 0; i < oldM; i++) {
            TreeMap<K,V> map = table[i];
            for (K key : map.keySet()) {
                newTable[hash(key)].put(key,map.get(key));
            }
        }
        this.table = newTable;
    }

    /**
     * 删除哈希表中key对应的键值对，返回value
     * @param key
     * @return
     */
    public V remove(K key) {
        TreeMap<K,V> map = table[hash(key)];
        if (!map.containsKey(key)) {
            throw new NoSuchElementException("no such element! remove fail");
        }
        V ret = map.remove(key);
        size --;
        return ret;
    }

    /**
     * 将哈希表中key对应的元素更新为value
     * @param key
     * @param value
     */
    public void set(K key,V value) {
        if (!table[hash(key)].containsKey(key)) {
            throw new NoSuchElementException("no such element! update fail");
        }
        table[hash(key)].put(key,value);
    }

    public boolean contains(K key) {
        return table[hash(key)].containsKey(key);
    }

    public V get(K key) {
        return table[hash(key)].get(key);
    }
}